package prac4;
/**
 * Implements the list data type using linked nodes.
 * 
 * @author			Maria Garcia de la Banda
 * @modified		Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
 *					Brendon Taylor (Feb 2010) - JavaDoc
 *					Maria Garcia de la Banda (March 2011) - details
 *					Menghong Li (Aug 2011)- details
 *					Leo Li & Ian Moriarty - Expanded to meet the requirements of Prac 4
 * @since			15th March 2007
 * @invariant		(1) head points to the first node in the list, or null if empty
 * @invariant		(2) each node points to the next node in the position in the list
 * @input			none
 * @output			only for regression testing
 * @errorHandling	none
 * @knownBugs		none
 */

public class UnsortedLinkedStringList {
	/** reference to the first node in the list */
	private Node head;

	/**
	 * Implements each linked node.
	 *
	 * @author	Maria Garcia de la Banda
	 * @modified Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
	 *			Brendon Taylor (Feb 2010) - JavaDoc
	 *			Maria Garcia de la Banda (March 2011) - details
	 *			Menghong Li (Aug 2011) - details
	 */
	private class Node { 
		/** data in the node */
		private String item; 
		/** link to the successor node */
		private Node successor;

		/**
		 * Creates a new node of the list wit the appropriate data.
		 *
		 * @param newItem to be stored in this node
		 * @param newSuccessor reference to the successor node in the list
		 * @post	a node object is created with data newItem and linked to 
		 *		newSuccessor
		 * @complexity	best and worst case: O(1)
		 */
		public Node(String newItem, Node newSuccessor) { 
			item = newItem;
			successor = newSuccessor;
		}
	}

	/**
	 * Creates an empty object of the class, i.e., an empty list of integers, 
	 * Since the list is implemented with a linked list, the size is not needed.
	 * 
	 * @post		an empty list object is created
	 * @complexity	best and worst case: O(1)
	 */
	public UnsortedLinkedStringList() {
		head = null;
	}

	/**
	 * Same as above, but allows the user to provide the size (disregarded).
	 * This method is included to keep the same interface as the List 
	 * implemented with arrays.
	 * 
	 * @param		size of the linked list (ignored)
	 * @post		an empty list object is created
	 * @complexity	best and worst case: O(1)
	 */
	public UnsortedLinkedStringList(int size) {
		this();
	}

	/**
	 * Determines whether the list is empty.
	 * 
	 * @return		true if the list is empty, false otherwise
	 * @complexity	best and worst case: O(1)
	 */
	public boolean isEmpty() {
		return (head == null);
	}

	/**
	 * Determines whether the list is full.
	 * Since it is implemented with linked nodes, it will never be.
	 * Method introduced for consistency with the list implemented with arrays.
	 * 
	 * @return	 false 
	 * @complexity best and worst case: O(1)
	 */
	public boolean isFull() {
		return false;
	}
 
	/**
	 * Resets the list to an empty state.
	 * 
	 * @post		the list is emptied
	 * @complexity	best and worst case: O(1)
	 */
	public void reset() {		
		head = null;
	}

	/**
	 * Adds a new node (containing the input item) as the head of the list.
	 * 
	 * @param		newItem to add to this linked list 
	 * @return		true if the list contains all previous items in the same
	 *				relative position, plus the input item as the first item,
	 *				false if it cannot add the item.
	 * @complexity	best and worst case: O(1)
	 */
	public boolean addFirst(String newItem) {	
		head = new Node(newItem, head);
		return true;
	}

	/**
	 * Internal method used to obtain the (address of the) first node (if any). 
	 * containing the input item.
	 * 
	 * @param		item to find
	 * @return		null if the item does not appear in the list, and
	 *				otherwise, the address of the first node the item appears in
	 * @complexity	best case: O(1) (first item)<br>
	 * 				worse case: O(N) (not there)
	 */
	private Node findLin(String item) {
		Node current = head;
		while(current != null && current.item.compareTo(item) != 0) {
				current = current.successor;
		}
		return current;
	}

	/**
	 * Deletes the first node (if any) containing the input item.
	 * 
	 * @param		item to be deleted 
	 * @post		true if the list contains all previous items in the same
	 *				relative position, except the first occurrence of item,
	 *				false if it does not appear.
	 * @throws		Exception thrown if item does not exist in the linked list
	 * @complexity	best case: O(1) (first item)<br>
	 * 				worst case: O(N) (not there)
	 */
	public boolean deleteItem(String item) throws Exception {
		if (isEmpty()) {			// list is empty			
			throw new Exception("empty list");
		} else if (head.item.compareTo(item) == 0) { // delete first
			head = head.successor; 
			return true;
		} else {
			Node current = head.successor;
			Node previous = head;
			
			while (current != null && current.item.compareTo(item) != 0) {
					previous = current;
					current = current.successor;						
			}

			if (current == null) {	// item not found 
					throw new Exception("not found");
			} else {				 // item found
					previous.successor = current.successor;
				return true;
			}
		}
	}

	/**
	 * Implements a list iterator.
	 * 
	 * @author	 Maria Garcia de la Banda
	 * @modified	Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
	 *			 Brendon Taylor (Feb 2010) - JavaDoc
	 *			 Menghong Li (Aug 2011) - details
	 */
	public class ListIterator {

		/** points to the next node the user can use */
		private Node current;
		/** points to the node used previously by the user */
		private Node previous;

		/**
		 * Creates a new iterator for the current list object.
		 *
		 * @post		an iterator object is created with current pointing
		 *				to the head and previous to null
		 * @complexity	best and worst case: O(1) 
		 */
		public ListIterator() {
			current = head; 
			previous = null;
		}

		/**
		 * Used to check whether the iterator has already gone through all items 
		 * already, or there are some left to iterate.
		 * 
		 * @return		true if there is an element that has not yet
		 *				been iterated over, false otherwise
		 * @complexity	best and worst case: O(1)
		 */
		public boolean	hasNext() {
			return (current != null);
		}

		/**
		 * Returns the item of the node currently pointed to by the iterator. 
		 * If all nodes have been iterated over, it throws an exception.
		 * 
		 * @return		the item of the node currently pointed to by the iterator
		 * @throws		Exception thrown if no item exists *here*
		 * @post		if there is an element that has not yet been 
		 *				iterated over, it returns it.
		 * @complexity	best and worst case: O(1)
		 */
		public String peek() throws Exception {	
			if (hasNext()) {
				return current.item;
			}

			throw new Exception("Cannot peek here");
		}

		/**
		 * Returns the item of the node currently pointed to by the iterator. 
		 * and moves to the next. If all nodes had already been iterated over, 
		 * it throws an exception.
		 * 
		 * @return		the item of the node currently pointed to by the iterator
		 * @throws		Exception thrown when at the end of the list 
		 * @post		if there is an element that has not yet been 
		 *				iterated over, it returns it and moves over it. 
		 * @complexity	best and worst case: O(1)
		 */
		public String next() throws Exception {
			if (hasNext()) {
				String temp = current.item;
				previous = current;
				current = current.successor;
				return temp;
			}
			
			throw new Exception("No next");
		}
		
		/**
		 * Returns the item of the node currently pointed to by the iterator. 
		 * deletes the node and moves to the next. If all nodes had already 
		 * been iterated over, it throws an exception.
		 * 
		 * @throws		Exception thrown if the node can't be found 
		 * @post		if there is an element that has not yet been 
		 *				iterated over, it deletes it and moves to the next.
		 * @complexity	best and worst case: O(1)
		 */
		public void delete() throws Exception {
			if (hasNext()) {
				if (previous == null) {		 
					head = head.successor;
					current = head;
				} else {
					previous.successor = current.successor;
					current = current.successor;
				}		
			} else {
				throw new Exception("cannot delete here");
			} 
		}
		
		/**
		 * Resets the iterator to be pointing to the head node.
		 * 
		 * @post		the iterator is pointing at the start of the list
		 * @complexity	best and worst case: O(1)
		 */
		public void reset(){
			current = head;
			previous = null;
		}
		
		/**
		 * Inserts a new node into the list at the current position of the iterator.
		 * 
		 * @param		newItem the string to be inserted into the list
		 * @post		a new node has been inserted at the current position
		 * @complexity	best and worst case: O(1)
		 */
		public void addHere(String newItem){
			if(isEmpty()){
				// The list is empty and the new node is the head node
				head = new Node(newItem,null);
				previous = head;
				current = previous.successor;
			} else if (previous == null){
				// We're inserting the new node at the start of the list and it replaces the head node
				head = new Node(newItem,head);
				previous = head;
				current = head.successor;
			} else {
				// We're inserting the new node at some other point in the list
				previous.successor = new Node(newItem, current);
				previous = previous.successor;
				current = previous.successor;
			}
		}
	}

	/**
	 * Creates and returns a new iterator for the current list object.
	 * 
	 * @return		reference to the new list iterator
	 * @post		an iterator for the current list object is created 
	 * @complexity	best and worst case: that of ListIterator()
	 * @see		 ListIterator#ListIterator()
	 */
	public ListIterator iterator() {
		return (new ListIterator());
	}

	/**
	 * Used to convert the elements of the queue into string format, following the order front-to-back.
	 * 
	 * @return	String representation of the list
	 * @post	returns a string which represents all the elements in the list	
	 * @complexity	Best and worst case: O(N)*O_+ (i.e., O(N) multiplied 
	 *			by whatever complexity + has)
	 */
	public String toString() {
		Node current = head;
		String temp = "";
		
		while(current != null) {	 
			temp += " " + current.item;
			current = current.successor;
		}

		return temp;
	}

	/*********************** REGRESSION TESTING CODE **********************/

	/**
	 * Two test cases: empty lists and non-empty lists. 
	 * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
	 */
	private static void testIsEmpty() {	 
		UnsortedLinkedStringList myList = new UnsortedLinkedStringList();
		System.out.println("TESTING isEmpty()");
		System.out.println("Expected true, got " + myList.isEmpty());
		myList.addFirst("9");
		System.out.println("Expected false, got " + myList.isEmpty());
		myList.addFirst("0");
		System.out.println("Expected false, got " + myList.isEmpty());
		myList.addFirst("1");
		myList.addFirst("2");
		myList.addFirst("14");
		System.out.println("Expected false, got " + myList.isEmpty());
	}

	/**
	 * Two test cases: full lists and non-full lists. 
	 * Boundary analysis gives three cases: 0 elements, 1, and many (5).
	 */
	private static void testIsFull() {		
		UnsortedLinkedStringList myList = new UnsortedLinkedStringList();
		System.out.println("TESTING isFull()");
		System.out.println("Expected false, got " + myList.isFull());
		myList.addFirst("9");
		System.out.println("Expected false, got " + myList.isFull());
		myList.addFirst("0");
		myList.addFirst("1");
		myList.addFirst("2");
		myList.addFirst("14");
		System.out.println("Expected false, got " + myList.isFull());
	}

	/**
	 * One test case: a list of any length. 
	 * Boundary analysis gives three cases: 0 elements, 1, and many (5).
	 */
	private static void testAddFirst() {	
		UnsortedLinkedStringList myList = new UnsortedLinkedStringList(5);
		System.out.println("TESTING addFirst()");
		System.out.println("Expected true, got " + myList.addFirst("9"));
		System.out.println("	with list 9, got " + myList);
		System.out.println("Expected true, got " + myList.addFirst("0"));
		System.out.println("	with list 0 9, got " + myList);
		myList.addFirst("1");
		myList.addFirst("14");
		System.out.println("Expected true, got " + myList.addFirst("20"));
		System.out.println("	with list 20 14 1 0 9, got " + myList);
	}

	/**
	 * Two test cases: the item is not in the list and it is in it. 
	 * Subclasses for the class in which the item is in: is the first slot 
	 *		the last, or in the middle. 
	 * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
	 *		used-1, and some slot in the middle.
	 * 
	 * @throws		Expection thrown if item can not be deleted
	 */
	private static void testDeleteItem() throws Exception {		 
		UnsortedLinkedStringList myList = new UnsortedLinkedStringList();
		myList.addFirst("8");
		myList.addFirst("7");
		myList.addFirst("5");
		myList.addFirst("5");
		myList.addFirst("4");
		myList.addFirst("3");
		myList.addFirst("2");
		myList.addFirst("1");
		myList.addFirst("0");
		System.out.println("TESTING deleteItem()");
		System.out.println("Expected true, got " + myList.deleteItem("5"));
		System.out.println("	with list 0 1 2 3 4 5 7 8, got " + myList);
		System.out.println("Expected true, got " + myList.deleteItem("1"));
		System.out.println("	with list 0 2 3 4 5 7 8, got " + myList);
		System.out.println("Expected true, got " + myList.deleteItem("0"));
		System.out.println("	with list 2 3 4 5 7 8, got " + myList);
		System.out.println("Expected true, got " + myList.deleteItem("7"));
		System.out.println("	with list 2 3 4 5 8, got " + myList);
		System.out.println("Expected true, got " + myList.deleteItem("8"));
		System.out.println("	with list 2 3 4 5, got " + myList);
		System.out.print("Expected exception ");
		
		try {
			myList.deleteItem("9");
		}
		catch(Exception e) {
			System.out.println(e);
			return;
		}
		
		System.out.println("but no exception thrown");
	}

	/**
	 * Two test cases: the item is not in the list and it is in it.
	 * Subclasses for the class in which the item is in: is the first slot 
	 *		the last, or in the middle.
	 * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
	 *		used-1, and some slot in the middle.
	 */
	private static void testFindLin() {	 
		UnsortedLinkedStringList myList = new UnsortedLinkedStringList(8);
		myList.addFirst("0");
		myList.addFirst("1");
		myList.addFirst("2");
		myList.addFirst("14");
		myList.addFirst("20");
		myList.addFirst("30");
		myList.addFirst("40");
		myList.addFirst("50");
		System.out.println("TESTING findLin()");
		System.out.println("Expected null, got " + myList.findLin("9"));
		System.out.println("Expected 0, got " + myList.findLin("0").item);
		System.out.println("Expected 1, got " + myList.findLin("1").item);
		System.out.println("Expected 14, got " + myList.findLin("14").item);
		System.out.println("Expected 40, got " + myList.findLin("40").item);
		System.out.println("Expected 50, got " + myList.findLin("50").item);
	}

	/**
	 * @param		args command-line arguments
	 */
	public static void main(String[] args) {
		try {	
			testIsEmpty();
			testIsFull();
			testAddFirst();
			testDeleteItem();
			testFindLin();
		}
		catch(Exception e) {
			System.out.println(" Error, unexpected exception: " + e);
		}
	}
}